package com.spirng.leetcode.day04;

public class Test459 {
    public boolean repeatedSubstringPattern(String s) {
        String t=s+s;
        t=t.substring(1,t.length()-1);
        char[] TStr = t.toCharArray();
        char[] Str = s.toCharArray();
        int[] next = next(s.toCharArray());
        int j=0;
        for (int i = 0; i < TStr.length; i++) {
            while (j>0&&Str[j]!=TStr[i]){
                j=next[j-1];
            }
            if(Str[j]==TStr[i]){
                j++;
            }
            if(j==Str.length){
                return true;
            }
        }
        return false;
    }
    public static int [] next(char[] s){
        int [] next =new int[s.length];
        int j=0;
        next[0]=0;
        for (int i = 1; i < s.length; i++) {
            while (j>0&&s[j]!=s[i]){
                j=next[j-1];
            }
            if(s[j]==s[i]){
                j++;
            }
            next[i]=j;
        }
        return next;
    }
}
